package leetcode

import "strconv"

// Definition for a binary tree node.
type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

// https://leetcode.com/problems/find-duplicate-subtrees/
// Find Duplicate Subtrees
func findDuplicateSubtrees(root *TreeNode) []*TreeNode {
	hashMap, res := make(map[string]int), make([]*TreeNode, 0)
	var postTraversal func(*TreeNode) string
	postTraversal = func(node *TreeNode) string {
		if node == nil {
			return "#,"
		}
		ans := ""
		ans += postTraversal(node.Left)
		ans += postTraversal(node.Right)
		ans += strconv.Itoa(node.Val) + ","
		if v, ok := hashMap[ans]; ok && v == 1 {
			res = append(res, node)
		}
		hashMap[ans] = hashMap[ans] + 1
		return ans
	}
	postTraversal(root)
	return res
}
